package Graph.graphWithNoweight.hamilton;

import Graph.graphWithNoweight.dfs.Graph;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/4 12:39
 * @Version 1.0
 *
 * 哈密尔顿算法  回溯框架
 * 哈密尔顿路径：从一个点出发，沿着边行走，经过每个顶点恰好一次，不会到原点
 * 哈密尔顿回路：从一个点出发，沿着边行走，经过每个顶点恰好一次，之后再回到出发点
 */
public class HamiltonLoop {
    private Graph G;
    private boolean[] visited;

    private int pre[];
    private int end;

    public HamiltonLoop(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        pre = new int[G.V()];
        end = -1;
        //既然是判断哈密尔顿回路，那么一定是过0这个顶点的。
        dfs(0,0,G.V());
    }

    //left 代表还剩几个顶点没有被访问过。
    private boolean dfs(int v,int parent,int left) {
        visited[v] = true;
        pre[v] = parent;
        left--;
        if(left==0 && G.hasEdge(v,0)){
            //要判别 v这个节点是否能回到原点0
            end = v;
            return true;
        }
        for(int w:G.adj(v)){
            if(!visited[w]){
                if(dfs(w,v,left)){
                    return true;
                };
            }else if(w==0 && left==0){
                //w==0说明就是回到 原点了 ,,allVisited 为true说明就是全都遍历过了，符合哈密尔顿回路
                end = v;
                return true;
            }
        }
        // 这里设置回溯条件，，如果上面条件都没有满足的话，那么只能返回false了。
        visited[v] = false;
        return false;
    }

    private boolean allVisited() {
        for(int v=0;v<G.V();v++){
            if(!visited[v]){
                return false;
            }
        }
        return true;
    }

    public ArrayList<Integer> result(){
        ArrayList<Integer> res = new ArrayList<>();
        if(end == -1){
            return res;
        }
        //倒退获取路劲
        int cur = end;
        while (cur!=0){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(0);
        Collections.reverse(res);
        return res;
    }


    public static void main(String[] args) {
        Graph g = new Graph("g3.txt");
        HamiltonLoop graphDFS = new HamiltonLoop(g);
        System.out.println(graphDFS.result());
    }
}
